package cn.bouncyslime.dataStructures.linearList;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * 合并两个线性表（顺序表示），其中的元素按值非递减有序排列
 * 作者：张一卓
 * 创建日期：2020/9/11
 */
@Slf4j
public class MergeList {
    public static void main(String[] args) {
        int[] array = {3, 5, 8, 11};
        int[] array2 = {2, 6, 8, 9, 11, 15, 20};
        int[] result = new MergeList().merge(array, array2, array.length + array2.length);
        log.info("resultArray: " + Arrays.toString(result));
    }

    public int[] merge(int[] array, int[] array2, int newArrayLength){
        int[] resultArray = new int[newArrayLength];
        int i = 0, j = 0;
        int resultIndex = 0;
        // 遍历两个数组，直到遍历完较短的数组
        while (i < array.length && j <array2.length){
            int a = array[i];
            int b = array2[j];
            if (a < b){
                insert(resultArray, resultIndex++, a);
                i++;
            }else {
                insert(resultArray, resultIndex++, b);
                j++;
            }
        }
        // 在遍历完较短的数组之后，将较长的数组添加到结果数组的剩余部分
        while (i < array.length){
            insert(resultArray, resultIndex++, array[i]);
            i++;
        }
        while (j < array2.length){
            insert(resultArray, resultIndex++, array2[j]);
            j++;
        }
        return resultArray;
    }

    private void insert(int[] array, int index, int element){
//        if (array == null || array.length == 0){
//            array = new int[10];
//        }
//        if (index >= array.length){
//            int[] dest = new int[array.length * 2];
//            for (int i = 0; i<array.length; i++){
//                dest[i] = array[i];
//            }
//            array = dest;
//        }
        array[index] = element;
    }
}
